Top%2Dk query evaluation in sensor networks under query response time constraint.

Keyword Search in Databases

Advances in Knowledge Discovery and Data Mining

Advances in Knowledge Discovery and Data Mining

Database and XML Technologies %2D 7th International XML Database Symposium

Matching dependence%2Drelated queries in the system dependence graph.

Energy%2Defficient top%2Dk query processing in wireless sensor networks.

Matching Top%2Dk Answers of Twig Patterns in Probabilistic XML.

Discovering Burst Areas in Fast Evolving Graphs.

Chasing Tree Patterns under Recursive DTDs.

Detecting Leaders from Correlated Time Series.

Fires on the Web Towards Efficient Exploring Historical Web Graphs.

Querying Large Graph Databases.
� Graph is a powerful modeling tool � Graph data is everywhere (e.g. chemistry, biology, image, vision, social networks, the Web, etc.)
Querying Large Graph Databases.
� Graph is a powerful modeling tool � Graph data is everywhere (e.g. chemistry, biology, image, vision, social networks, the Web, etc.)


Probabilistic ranking over relations.

Research on geographic information sharing in different cultural backgrounds.

Online Time Interval Top%2Dk Queries in Wireless Sensor Networks.

Fast Single%2DPair SimRank Computation.

Finding maximal cliques in massive networks by H%2A%2Dgraph.
Maximal clique enumeration (MCE) is a fundamental problem in graph theory and has important applications in many areas such as social network analysis and bioinformatics. The problem is extensively studied; however, the best existing algorithms require memory space linear in the size of the input graph. This has become a serious concern in view of the massive volume of today’s fastgrowing network graphs. Since MCE requires random access to different parts of a large graph, it is difficult to divide the graph into smaller parts and process one part at a time, because either the result may be incorrect and incomplete, or it incurs huge cost on merging the results from different parts. We propose a novel notion, H ∗-graph, which defines the core of a network and extends to encompass the neighborhood of the core for MCE computation. We propose the first external-memory algorithm for MCE (ExtMCE) that uses theH ∗-graph to bound the memory usage. We prove both the correctness and completeness of the result computed by ExtMCE. Extensive experiments verify that ExtMCE efficiently processes large networks that cannot be fit in the memory. We also show that the H ∗-graph captures important properties of the network; thus, updating the maximal cliques in the H ∗-graph retains the most essential information, with a low update cost, when it is infeasible to perform update on the entire network.
Connected substructure similarity search.

On Maximal Contained Rewriting of Tree Pattern Queries Using Views.

Duplicate%2DInsensitive Order Statistics Computation over Data Streams.
Abstract—Duplicates in data streams may often be observed by the projection on a subspace and/or multiple recordings of objects. Without the uniqueness assumption on observed data elements, many conventional aggregates computation problems need to be further investigated due to their duplication sensitive nature. In this paper, we present novel, space-efficient, one-scan algorithms to continuously maintain duplicate insensitive order sketches so that rank-based queries can be approximately processed with a relative rank error guarantee ǫ in the presence of data duplicates. Besides the space efficiency, the proposed algorithms are time-efficient and highly accurate. Moreover, our techniques may be immediately applied to the heavy hitter problem against distinct elements and to the existing fault-tolerant distributed communication techniques. A comprehensive performance study demonstrates that our algorithms can support real-time computation against high speed data streams.
Keyword Search in Relational Databases A Survey.
The integration of DB and IR provides flexible ways for users to query information in the same platform [6, 2, 3, 7, 5, 28]. On one hand, the sophisticated DB facilities provided by RDBMSs assist users to query well-structured information using SQL. On the other hand, IR techniques allow users to search unstructured information using keywords based on scoring and ranking, and do not need users to understand any database schemas.
Duplicate%2DInsensitive Order Statistics Computation over Data Streams.
Abstract—Duplicates in data streams may often be observed by the projection on a subspace and/or multiple recordings of objects. Without the uniqueness assumption on observed data elements, many conventional aggregates computation problems need to be further investigated due to their duplication sensitive nature. In this paper, we present novel, space-efficient, one-scan algorithms to continuously maintain duplicate insensitive order sketches so that rank-based queries can be approximately processed with a relative rank error guarantee ǫ in the presence of data duplicates. Besides the space efficiency, the proposed algorithms are time-efficient and highly accurate. Moreover, our techniques may be immediately applied to the heavy hitter problem against distinct elements and to the existing fault-tolerant distributed communication techniques. A comprehensive performance study demonstrates that our algorithms can support real-time computation against high speed data streams.
Guest Editors%27 Introduction Special Section on Mining Large Uncertain and Probabilistic Databases.

Adaptive relaxation for querying heterogeneous XML data sources.

Context%2DSensitive Document Ranking.

iGraph A Framework for Comparisons of Disk%2DBased Graph Indexing Techniques.
Graphs are of growing importance in modeling complex structures such as chemical compounds, proteins, images, and program dependence. Given a query graph Q, the subgraph isomorphism problem is to find a set of graphs containing Q from a graph database, which is NP-complete. Recently, there have been a lot of research efforts to solve the subgraph isomorphism problem for a large graph database by utilizing graph indexes. By using a graph index as a filter, we prune graphs that are not real answers at an inexpensive cost. Then, we need to use expensive subgraph isomorphism tests to verify filtered candidates only. This way, the number of disk I/Os and subgraph isomorphism tests can be significantly minimized. The current practice for experiments in graph indexing techniques is that the author of a newly proposed technique does not implement existing indexes on his own code base, but instead uses the original authors ’ binary executables and reports only the wall clock time. However, we observe this practice may result in several problems. In order to address these problems, we have made significant efforts in implementing all representative indexing methods on a common framework called iGraph. Unlike existing implementations which either use (full or partial) in-memory representations or rely on OS file system cache without guaranteeing real disk I/Os, we have implemented these indexes on top of a storage engine that guarantees real disk I/Os. Through extensive experiments using many synthetic and real datasets, we also provide new empirical findings in the performance of the full disk-based implementations of these methods. 1.
Sliding%2Dwindow top%2Dk queries on uncertain streams.
Query processing on uncertain data streams has attracted a lot of attentions lately, due to the imprecise nature in the data generated from a variety of streaming applications, such as readings from a sensor network. However, all of the existing works on uncertain data streams study unbounded streams. This paper takes the first step towards the important and challenging problem of answering sliding-window queries on uncertain data streams, with a focus on arguably one of the most important types of queries—top-k queries. The challenge of answering sliding-window top-k queries on uncertain data streams stems from the strict space and time requirements of processing both arriving and expiring tuples in high-speed streams, combined with the difficulty of coping with the exponential blowup in the number of possible worlds induced by the uncertain data model. In this paper, we design a unified framework for processing sliding-window top-k queries on uncertain streams. We show that all the existing top-k definitions in the literature can be plugged into our framework, resulting in several succinct synopses that use space much smaller than the window size, while are also highly efficient in terms of processing time. In addition to the theoretical space and time bounds that we prove for these synopses, we also present a thorough experimental report to verify their practical efficiency on both synthetic and real data. 1.
ICDM Workshops 2009

Web Information Systems Engineering %2D WISE 2009

Indexing the Function An Efficient Algorithm for Multi%2Ddimensional Search with Expensive Distance Functions.

Minimal common container of tree patterns.

Progressive skyline query evaluation and maintenance in wireless sensor networks.

Context%2Dsensitive document ranking.

A Uniform Framework for Ad%2DHoc Indexes to Answer Reachability Queries on Large Graphs.

Materialized View Selection in XML Databases.


Finding the influence set through skylines.
Given a set P of products, a set O of customers, and a product p ∈ P, a bichromatic reverse skyline query retrieves all the customers in O that do not find any other product in P to be absolutely better than p. More specifically, a customer o ∈ O is in the reverse skyline of p ∈ P if and only no other product in P better matches the preference of o on all dimensions. The only existing bichromatic reverse skyline algorithm, which we refer to as basic, is designed for uncertain data. This paper focuses on traditional datasets, where each object is a precise point. Since a precise point can be regarded as a special uncertain object, basic can still be applied. However, as precise data are inherently easier to handle than uncertain data, one should expect that basic can be further improved by taking advantage of the reduced problem complexity. Indeed, we observe several non-trivial heuristics that can optimize the access order to achieve stronger pruning power. Motivated by this, we propose a new algorithm called BRS, and prove that BRS never entails more I/Os than basic. Besides our theoretical analysis, we also perform extensive experiments to show that in practice BRS usually outperforms basic by a large factor. For example, when both P and O follow the anti-correlated distribution, BRS is faster than basic by an order of magnitude. Finally, we address a new variation of bichromatic reverse skyline search where the conventional definition of dynamic skylines no longer makes sense. 1.

On%2Dline exact shortest distance query processing.

Probabilistic Skyline Operator over Sliding Windows.
Abstract — Skyline computation has many applications including multi-criteria decision making. In this paper, we study the problem of efficient processing of continuous skyline queries over sliding windows on uncertain data elements regarding given probability thresholds. We first characterize what kind of elements we need to keep in our query computation. Then we show the size of dynamically maintained candidate set and the size of skyline. We develop novel, efficient techniques to process a continuous, probabilistic skyline query. Finally, we extend our techniques to the applications where multiple probability thresholds are given or we want to retrieve “top-k ” skyline data objects. Our extensive experiments demonstrate that the proposed techniques are very efficient and handle a high-speed data stream in real time. I.
Scalable Keyword Search on Large Data Streams.

Spatial Range Querying for Gaussian%2DBased Imprecise Query Objects.

Querying Communities in Relational Databases.
Abstract — Keyword search on relational databases provides users with insights that they can not easily observe using the traditional RDBMS techniques. Here, an l-keyword query is specified by a set of l keywords, {k1, k2,  ·  ·  · , kl}. It finds how the tuples that contain the keywords are connected in a relational database via the possible foreign key references. Conceptually, it is to find some structural information in a database graph, where nodes are tuples and edges are foreign key references. The existing work studied how to find connected trees for an l-keyword query. However, a tree may only show partial information about how those tuples that contain the keywords are connected. In this paper, we focus on finding communities for an l-keyword query. A community is an induced subgraph that contains all the l-keywords within a given distance. We propose new efficient algorithms to find all/top-k communities which consume small memory, for an l-keyword query. For topk l-keyword queries, our algorithm allows users to interactively enlarge k at run time. We conducted extensive performance studies using two large real datasets to confirm the efficiency of our algorithms. I.
Context%2DAware Object Connection Discovery in Large Graphs.

Topic Distributions over Links on Web.
Abstract—It is well known that Web users create links with different intentions. However, a key question, which is not well studied, is how to categorize the links and how to quantify the strength of the influence of a web page on another if there is a link between the two linked web pages. In this paper, we focus on the problem of link semantics analysis, and propose a novel supervised learning approach to build a model, based on a training link-labeled and link-weighted graph where a link-label represents the category of a link and a link-weight represents the influence of one web page on the other in a link. Based on the model built, we categorize links and quantify the influence of web pages on the others in a large graph in the same application domain. We discuss our proposed approach, namely Pairwise Restricted Boltzmann Machines (PRBMs), and conduct extensive experimental studies to demonstrate the effectiveness of our approach using large real datasets. I.
Efficient Discovery of Frequent Correlated Subgraph Pairs.
The recent proliferation of graph data in a wide spectrum of applications has led to an increasing demand for advanced data analysis techniques. In view of this, many graph mining techniques, such as frequent subgraph mining and correlated subgraph mining, have been proposed. In many applications, both frequency and correlation play an important role. Thus, this paper studies a new problem of mining the set of frequent correlated subgraph pairs. A simple algorithm that combines existing algorithms for mining frequent subgraphs and correlated subgraphs results in a multiplication of the mining operations, the majority of which are redundant. We discover that most of the graphs correlated to a common graph are also highly correlated. We establish theoretical foundations for this finding and derive a tight lower bound on the correlation of any two graphs that are correlated to a common graph. This theoretical result leads to the design of a very effective skipping mechanism, by which we skip the processing of a majority of graphs in the mining process. Our algorithm, FCP-Miner, is a fast approximate algorithm, but we show that the missing pairs are only a small set of marginally correlated pairs. Extensive experiments verify both the efficiency and effectiveness of FCP-Miner.
Finding Hidden Structures in Relational Databases.

Top%2Dk Correlative Graph Mining.

Monitoring path nearest neighbor in road networks.
This paper addresses the problem of monitoring the k nearest neighbors to a dynamically changing path in road networks. Given a destination where a user is going to, this new query returns the k-NN with respect to the shortest path connecting the destination and the user’s current location, and thus provides a list of nearest candidates for reference by considering the whole coming journey. We name this query the k-Path Nearest Neighbor query (k-PNN). As the user is moving and may not always follow the shortest path, the query path keeps changing. The challenge of monitoring the k-PNN for an arbitrarily moving user is to dynamically determine the update locations and then refresh the k-PNN efficiently. We propose a three-phase Best-first Network Expansion (BNE) algorithm for monitoring the k-PNN and the corresponding shortest path. In the searching phase, the BNE finds the shortest path to the destination, during which a candidate set that guarantees to include the k-PNN is generated at the same time. Then in the verification phase, a heuristic algorithm runs for examining candidates’ exact distances to the query path, and it achieves significant reduction in the number of visited nodes. The monitoring phase deals with computing update locations as well as refreshing the k-PNN in different user movements. Since determining the network distance is a costly process, an expansion tree and the candidate set are carefully maintained by the BNE algorithm, which can provide efficient update on the shortest path and the k-PNN results. Finally, we conduct extensive experiments on real road networks and show that our methods achieve satisfactory performance.
Keyword search in databases the power of RDBMS.

Microbenchmark.

Multimedia Data Buffering.
Most multimedia servers reported in the literature are designed to serve  multiple and independent video/audio streams. We think that, in future,  multimedia servers will also serve complete presentations. Multimedia  presentations provide unique opportunities to develop algorithms for  buffer management and admission control, as execution-time  consumption requirements of presentations are known a priori. In this  paper, we examine presentations in three different domains (heavyweight,  middleweight, and lightweight) and provide buffer management and  admission control algorithms for the three domains. We propose two  improvements (flattening and dynamic-adjustments) on the schedules  created for the heavyweight presentations. Results from a simulation  environment are presented.  Keywords: Multimedia presentations, buffer management,admission control,  flattening.  1. 
Multimedia Data Storage.
Protecting multimedia data from malicious computer users continues to grow in importance. Whether preventing unauthorized access to digital photographs, ensuring compliance with copyright regulations, or guaranteeing the integrity of a video teleconference, all multimedia applications require increased security in the presence of talented intruders. Specifically, as more and more files are preserved on disk the requirement to provide secure storage has become more important. This paper presents a survey of techniques for securely storing multimedia data, including theoretical approaches, prototype systems, and existing systems ready for employment. Due to the wide variety of potential solutions available, a prospective customer can easily become overwhelmed while researching an appropriate system for multimedia requirements. Since added security measures inevitably result in slower system performance, certain storage solutions provide a better fit for particular applications along a security/performance continuum. This paper provides an overview of the prominent characteristics of several systems to provide a foundation for selecting the most appropriate solution. Initially, the paper establishes a set of criteria for evaluating a storage solution based on confidentiality, integrity, availability, and performance. Then, using these criteria, the paper explains the relevant characteristics of select storage systems providing a comparison of the major differences. Finally, the paper examines specific applications of storage devices in the multimedia environment.
Multimedia Resource Scheduling.

XML Benchmarks.
With standardization efforts of a query language for XML documents drawing to a close, researchers and users increasingly focus their attention on the database technology that has to deliver on the new challenges that the sheer amount of XML documents produced by applications pose to data management: validation, performance evaluation and optimization of XML query processors are the upcoming issues. Following a long tradition in database research, the XML Store Benchmark Project provides a framework to assess an XML database&#039;s abilities to cope with a broad spectrum of different queries, typically posed in real-world application scenarios. The benchmark is intended to help both implementors and users to compare XML databases independent of their own, specific application scenario.
Continuous Multimedia Data Retrieval.

Application Benchmark.

Fast Probabilistic Ranking under x%2DRelation Model

Multiscale Representations for Fast Pattern Matching in Stream Time Series.

Stock prediction an event%2Ddriven approach based on bursty keywords.

Multiscale Representations for Fast Pattern Matching in Stream Time Series.

Making filters smart in distributed data stream environments.

Graph Clustering Based on Structural%2FAttribute Similarities.
The goal of graph clustering is to partition vertices in a large graph into different clusters based on various criteria such as vertex connectivity or neighborhood similarity. Graph clustering techniques are very useful for detecting densely connected groups in a large graph. Many existing graph clustering methods mainly focus on the topological structure for clustering, but largely ignore the vertex properties which are often heterogenous. In this paper, we propose a novel graph clustering algorithm, SA-Cluster, based on both structural and attribute similarities through a unified distance measure. Our method partitions a large graph associated with attributes into k clusters so that each cluster contains a densely connected subgraph with homogeneous attribute values. An effective method is proposed to automatically learn the degree of contributions of structural similarity and attribute similarity. Theoretical analysis is provided to show that SA-Cluster is converging. Extensive experimental results demonstrate the effectiveness of SA-Cluster through comparison with the state-of-the-art graph clustering and summarization methods. 1.
Query translation from XPath to SQL in the presence of recursive DTDs.
The interaction between recursion in XPATH and  recursion in DTDs makes it challenging to answer  XPATH queries on XML data that is stored in an  RDBMS via schema-based shredding. We present  a new approach to translating XPATH queries into  SQL queries with a simple least fixpoint (LFP) operator,  which is already supported by most commercial   RDBMS. The approach is based on our  algorithm for rewriting XPATH queries into regular   XPATH expressions, which are capable of capturing  both DTD recursion and XPATH queries in  a uniform framework. Furthermore, we provide  an algorithm for translating regular XPATH queries  to SQL queries with LFP, and optimization techniques  for minimizing the use of the LFP operator.
Optimizing updates of recursive XML views of relations.

Independence of Containing Patterns Property and Its Application in Tree Pattern Query Rewriting Using Views.

Semantics based Buffer Reduction for Queries over XML Data Streams.

Computing Structural Similarity of Source XML Schemas against Domain XML Schema.
In this paper, we study the problem of measuring structural similarities of large number of source schemas against a single domain schema, which is useful for enhancing the quality of searching and ranking big volume of source documents on the Web with the help of structural information. After analyzing the improperness of adopting existing edit-distance based methods, we propose a new similarity measure model that caters for the requirements of the problem. Given the asymmetric nature of the similarity comparisons of source schemas with a domain schema, similarity preserving rules and algorithm are designed to filter out uninteresting elements in source schemas for the purpose of optimizing the similarity computation. Based on the model, a basic algorithm and an improved algorithm are developed for structural similarity computation. The improved algorithm makes full use of a new coding scheme that is devised to reduce the number of comparisons. Complexities of both algorithms are analyzed and extensive experiments are conducted showing the significant performance gain achieved by the improved algorithm.
On Safety%2C Computability and Local Property of Web Queries.

Mining Multiple Time Series Co%2Dmovements.

Energy%2Defficient skyline query processing and maintenance in sensor networks.

Efficient Top%2Dk Search Across Heterogeneous XML Data Sources.

Supporting Keyword Queries on Structured Databases with Limited Search Interfaces.

A Holistic Algorithm for Efficiently Evaluating Xtwig Joins.

XPath Rewriting Using Multiple Views.
The standard approach for optimization of XPath queries by rewriting using views techniques consists in navigating inside a view’s output, thus allowing the usage of only one view in the rewritten query. Algorithms for richer classes of XPath rewritings, using intersection or joins on node identifiers, have been proposed, but they either lack completeness guarantees, or require additional information about the data. We identify the tightest restrictions under which an XPath can be rewritten in polynomial time using an intersection of views and propose an algorithm that works for any documents or type of identifiers. As an additional contribution, we analyze the complexity of the related problem of deciding if an XPath with intersection can be equivalently rewritten as one without intersection or union. 1.
Transforming Tree Patterns with DTDs for Query Containment Test.

A novel spectral coding in a large graph database.
Retrieving related graphs containing a query graph from a large graph database is a key issue in many graph-based applications, such as drug discovery and structural pattern recognition. Because sub-graph isomorphism is a NP-complete problem [4], we have to employ a filter-and-verification framework to speed up the search efficiency, that is, using an effective and efficient pruning strategy to filter out the false positives (graphs that are not possible in the results) as many as possible first, then validating the remaining candidates by subgraph isomorphism checking. In this paper, we propose a novel filtering method, a spectral encoding method, i.e. GCoding. Specifically, we assign a signature to each vertex based on its local structures. Then, we generate a spectral graph code by combining all vertex signatures in a graph. Based on spectral graph codes, we derive a necessary condition for sub-graph isomorphism. Then we propose two pruning rules for sub-graph search problem, and prove that they satisfy the no-false-negative requirement (no dismissal in answers). Since graph codes are in numerical space, we take this advantage and conduct efficient filtering over graph codes. Extensive experiments show that GCoding outperforms existing counterpart methods. 1.
Fast computing reachability labelings for large graphs with high compression rate.
There are numerous applications that need to deal with a large graph and need to query reachability between nodes in the graph. A 2-hop cover can compactly represent the whole edge transitive closure of a graph in O(|V |  · |E | 1/2) space, and be used to answer reachability query efficiently. However, it is challenging to compute a 2-hop cover. The existing approaches suffer from either large resource consumption or low compression rate. In this paper, we propose a hierarchical partitioning approach to partition a large graph G into two subgraphs repeatedly in a top-down fashion. The unique feature of our approach is that we compute 2-hop cover while partitioning. In brief, in every iteration of top-down partitioning, we provide techniques to compute the 2-hop cover for connections between the two subgraphs first. A cover is computed to cut the graph into two subgraphs, which results in an overall cover with high compression for the entire graph G. Two approaches are proposed, namely a node-oriented approach and an edge-oriented approach. Our approach can efficiently compute 2-hop cover for a large graph with high compression rate. Our extensive experiment study shows that the 2-hop cover for a graph with 1,700,000 nodes and 169 billion connections can be obtained in less than 30 minutes with a compression rate about 40,000 using a PC.
Finding time%2Ddependent shortest paths over large graphs.

Detection of Shape Anomalies A Probabilistic Approach Using Hidden Markov Models.

Pattern Matching over Cloaked Time Series.

Hierarchical Indexing Approach to Support XPath Queries.

Multiple Materialized View Selection for XPath Query Rewriting.
Abstract — We study the problem of answering XPATH queries using multiple materialized views. Despite the efforts on answering queries using single materialized view, answering queries using multiple views remains relatively new. We address two important aspects of this problem: multiple-view selection and equivalent multiple-view rewriting. With regards to the first problem, we propose an NFA-based approach (called VFILTER) to filter views that cannot be used to answer a given query. We then present the criterion for multiple view/query answerability. Based on the output of VFILTER, we further propose a heuristic method to identify a minimal view set that can answer a given query. For the problem of multiple-view rewriting, we first refine the materialized fragments of each selected view (like pushing selection), we then join the refined fragments utilizing an encoding scheme. Finally, we extract the result of the query from the materialized fragments of a single view. Experiments show the efficiency of our approach.
Fast Graph Pattern Matching.

Spotting Significant Changing Subgraphs in Evolving Graphs.

Response Time Constrained Top%2Dk Query Evaluation in Sensor Networks.

Monitoring Aggregate k%2DNN Objects in Road Networks.

Contained Rewritings of XPath Queries Using Views Revisited.


Integrating Multiple Data Sources for Stock Prediction.


Maximal Subspace Coregulated Gene Clustering.
Abstract—Clustering is a popular technique for analyzing microarray data sets, with n genes and m experimental conditions. As explored by biologists, there is a real need to identify coregulated gene clusters, which include both positive and negative regulated gene clusters. The existing pattern-based and tendency-based clustering approaches cannot directly be applied to find such coregulated gene clusters, because they are designed for finding positive regulated gene clusters. In this paper, in order to cluster coregulated genes, we propose a coding scheme that allows us to cluster two genes into the same cluster if they have the same code, where two genes that have the same code can be either positive or negative regulated. Based on the coding scheme, we propose a new algorithm for finding maximal subspace coregulated gene clusters with new pruning techniques. A maximal subspace coregulated gene cluster clusters a set of genes on a condition sequence such that the cluster is not included in any other subspace coregulated gene clusters. We conduct extensive experimental studies. Our approach can effectively and efficiently find maximal subspace coregulated gene clusters. In addition, our approach outperforms the existing approaches for finding positive regulated gene clusters. Index Terms—Gene expression data, clustering, coregulated gene clustering. Ç 1
Safety%2C domain independence and translation of complex value database queries.

Sliding%2Dwindow top%2Dk queries on uncertain streams.
Query processing on uncertain data streams has attracted a lot of attentions lately, due to the imprecise nature in the data generated from a variety of streaming applications, such as readings from a sensor network. However, all of the existing works on uncertain data streams study unbounded streams. This paper takes the first step towards the important and challenging problem of answering sliding-window queries on uncertain data streams, with a focus on arguably one of the most important types of queries—top-k queries. The challenge of answering sliding-window top-k queries on uncertain data streams stems from the strict space and time requirements of processing both arriving and expiring tuples in high-speed streams, combined with the difficulty of coping with the exponential blowup in the number of possible worlds induced by the uncertain data model. In this paper, we design a unified framework for processing sliding-window top-k queries on uncertain streams. We show that all the existing top-k definitions in the literature can be plugged into our framework, resulting in several succinct synopses that use space much smaller than the window size, while are also highly efficient in terms of processing time. In addition to the theoretical space and time bounds that we prove for these synopses, we also present a thorough experimental report to verify their practical efficiency on both synthetic and real data. 1.
Taming verification hardness an efficient algorithm for testing subgraph isomorphism.
Graphs are widely used to model complicated data semantics in many applications. In this paper, we aim to develop efficient techniques to retrieve graphs, containing a given query graph, from a large set of graphs. Considering the problem of testing subgraph isomorphism is generally NP-hard, most of the existing techniques are based on the framework of filtering-and-verification to reduce the precise computation costs; consequently various novel feature-based indexes have been developed. While the existing techniques work well for small query graphs, the verification phase becomes a bottleneck when the query graph size increases. Motivated by this, in the paper we firstly propose a novel and efficient algorithm for testing subgraph isomorphism, QuickSI. Secondly, we develop a new feature-based index technique to accommodate QuickSI in the filtering phase. Our extensive experiments on real and synthetic data demonstrate the efficiency and scalability of the proposed techniques, which significantly improve the existing techniques. 1.
A data mining proxy approach for efficient frequent itemset mining.

Fast Frequent Free Tree Mining in Graph Databases.

Advances in Data and Web Management

Cost%2DBased Query Optimization for Multi Reachability Joins.

Mining Closed Frequent Free Trees in Graph Databases.

Similarity Match Over High Speed Time%2DSeries Streams.

Summarizing Order Statistics over Data Streams with Duplicates.
A rank query is essentially to find a data element with a given rank against a monotonic order specified on data elements. Rank queries have several equivalent variations
Finding Top%2Dk Min%2DCost Connected Trees in Databases.
Existing keyword-search systems in relational databases require users to submit a complete query to compute answers. Often users feel “left in the dark” when they have limited knowledge about the data, and have to use a try-and-see method to modify queries and find answers. In this paper we propose a novel approach to keyword search in the relational world, called Tastier. A Tastier system can bring instant gratification to users by supporting type-ahead search, which finds answers “on the fly” as the user types in query keywords. A main challenge is how to achieve a high interactive speed for large amounts of data in multiple tables, so that a query can be answered efficiently within milliseconds. We propose efficient index structures and algorithms for finding relevant answers on-the-fly by joining tuples in the database. We devise a partition-based method to improve query performance by grouping relevant tuples and pruning irrelevant tuples efficiently. We also develop a technique to answer a query efficiently by predicting highly relevant complete queries for the user. We have conducted a thorough experimental evaluation of the proposed techniques on real data sets to demonstrate the efficiency and practicality of this new search paradigm.
A Logic%2DBased Approach to Mining Inductive Databases.

Time%2Ddependent event hierarchy construction.

Indexable PLA for Efficient Similarity Search.
Similarity-based search over time-series databases has been a hot research topic for a long history, which is widely used in many applications, including multimedia retrieval, data mining, web search and retrieval, and so on. However, due to high dimensionality (i.e. length) of the time series, the similarity search over directly indexed time series usually encounters a serious problem, known as the “dimensionality curse”. Thus, many dimensionality reduction techniques are proposed to break such curse by reducing the dimensionality of time series. Among all the proposed methods, only Piecewise Linear Approximation (PLA) does not have indexing mechanisms to support similarity queries, which prevents it from efficiently searching over very large timeseries databases. Our initial studies on the effectiveness of different reduction methods, however, show that PLA performs no worse than others. Motivated by this, in this paper, we re-investigate PLA for approximating and indexing time series. Specifically, we propose a novel distance function in the reduced PLA-space, and prove that this function indeed results in a lower bound of the Euclidean distance between the original time series, which can lead to no false dismissals during the similarity search. As a second step, we develop an effective approach to index these lower bounds to improve the search efficiency. Our extensive experiments over a wide spectrum of real and synthetic data sets have demonstrated the efficiency and effectiveness of PLA together with the newly proposed lower bound distance, in terms of both pruning power and wall clock time, compared with two stateof-the-art reduction methods, Adaptive Piecewise Constant Approximation (APCA) and Chebyshev Polynomials (CP).
Graph Indexing Tree   Delta g%3B%3D Grap.

On Tree Pattern Query Rewriting Using Views.

Adaptive scheduling for shared window joins over data streams.

CFP%2Dtree A compact disk%2Dbased structure for storing and querying frequent itemsets.

A dimensionality reduction algorithm and its application for interactive visualization.


Advances in Web%2DAge Information Management

Database and XML Technologies
This paper reports about our experience in developing the ERX  Data Management System, a system devised to collect data coming from different  XML data sources, and store them into a database in a way independent  of the source format; its query language, named ERX-QL, is able to query the  database and generate new XML documents. We developed the ERX Data  Management System to explore the possibility of integrating three different  basic technologies, Relational DBMS, Java and XSLT, under a unifying  framework which makes the system interoperable w.r.t. the particular adopted  technology (for example Relational vs Object-Oriented database technology);  hence, this framework is based on an Entity-Relationship-like Data Model  (ERX), which is not tied to any specific technical and/or commercial solution.
Fast Reachability Query Processing.

Fast Structural Join with a Location Function.

Fast Computation of Reachability Labeling for Large Graphs.
There are numerous applications that need to deal with a large graph and need to query reachability between nodes in the graph. A 2-hop cover can compactly represent the whole edge transitive closure of a graph in O(|V |  · |E | 1/2) space, and be used to answer reachability query efficiently. However, it is challenging to compute a 2-hop cover. The existing approaches suffer from either large resource consumption or low compression rate. In this paper, we propose a hierarchical partitioning approach to partition a large graph G into two subgraphs repeatedly in a top-down fashion. The unique feature of our approach is that we compute 2-hop cover while partitioning. In brief, in every iteration of top-down partitioning, we provide techniques to compute the 2-hop cover for connections between the two subgraphs first. A cover is computed to cut the graph into two subgraphs, which results in an overall cover with high compression for the entire graph G. Two approaches are proposed, namely a node-oriented approach and an edge-oriented approach. Our approach can efficiently compute 2-hop cover for a large graph with high compression rate. Our extensive experiment study shows that the 2-hop cover for a graph with 1,700,000 nodes and 169 billion connections can be obtained in less than 30 minutes with a compression rate about 40,000 using a PC.
Dual Labeling Answering Graph Reachability Queries in Constant Time.
Graph reachability is fundamental to a wide range of applications, including XML indexing, geographic navigation, Internet routing, ontology queries based on RDF/OWL, etc. Many applications involve huge graphs and require fast answering of reachability queries. Several reachability labeling methods have been proposed for this purpose. They assign labels to the vertices, such that the reachability between any two vertices may be decided using their labels only. For sparse graphs, 2-hop based reachability labeling schemes answer reachability queries efficiently using relatively small label space. However, the labeling process itself is often too time consuming to be practical for large graphs. In this paper, we propose a novel labeling scheme for sparse graphs. Our scheme ensures that graph reachability queries can be answered in constant time. Furthermore, for sparse graphs, the complexity of the labeling process is almost linear, which makes our algorithm applicable to massive datasets. Analytical and experimental results show that our approach is much more efficient than stateof-the-art approaches. Furthermore, our labeling method also provides an alternative scheme to tradeoff query time for label space, which further benefits applications that use tree-like graphs. 1

Fast Frequent Free Tree Mining in Graph Databases.

Suppressing model overfitting in mining concept%2Ddrifting data streams.

Is Frequency Enough for Decision Makers to Make Decisions%3F.

NUITS A Novel User Interface for Efficient Keyword Search over Databases.
The integration of database and information retrieval techniques provides users with a wide range of high quality services. We present a prototype system, called NUITS, for efficiently processing keyword queries on top of a relational
Towards multidimensional subspace skyline analysis.
The skyline operator is important for multicriteria decision-making applications. Although many recent studies developed efficient methods to compute skyline objects in a given space, none of them considers skylines in multiple subspaces simultaneously. More importantly, the fundamental
Text Classification without Negative Examples Revisit.

Approximate Processing of Massive Continuous Quantile Queries over High%2DSpeed Data Streams.

A false negative approach to mining frequent itemsets from high speed transactional data streams.

Efficient Computation of k%2DMedians over Data Streams Under Memory Constraints.

Finding centric local outliers in categorical%2Fnumerical spaces.

Answering XML Queries Using Path%2DBased Indexes A Survey.

Web Technologies Research and Development %2D APWeb 2005

False%2DNegative Frequent Items Mining from Data Streams with Bursting.

Accelerating XML Structural Join by Partitioning.

Text Classification without Labeled Negative Documents.

WIN An Effcient Data Placement Strategy for Parallel XML Databases.

Locating Motifs in Time%2DSeries Data.
The problem of locating motifs in real-valued, multivariate time series data involves the discovery of sets of recurring patterns embedded in the time series. Each set is composed of several non-overlapping subsequences and constitutes a motif because all of the included subsequences are similar. The ability to automatically discover such motifs allows intelligent systems to form endogenously meaningful representations of their environment through unsupervised sensor analysis. In this paper, we formulate a unifying view of motif discovery as a problem of locating regions of high density in the space of all time series subsequences. Our approach is efficient (sub-quadratic in the length of the data), requires fewer user-specified parameters than previous methods, and naturally allows variable length motif occurrences and nonlinear temporal warping. We evaluate the performance of our approach using four data sets from different domains including on-body inertial sensors and speech.
Parameter Free Bursty Events Detection in Text Streams.

Efficient Computation of the Skyline Cube.
Skyline has been proposed as an important  operator for multi-criteria decision making,  data mining and visualization, and user-preference  queries. In this paper, we consider  the problem of efficiently computing a  Skycube, which consists of skylines of all  possible non-empty subsets of a given set of  dimensions. While existing skyline computation  algorithms can be immediately extended  to computing each skyline query independently,  such &#034;shared-nothing&#034; algorithms are  inefficient. We develop several computation  sharing strategies based on e#ectively identifying  the computation dependencies among  multiple related skyline queries. Based on  these sharing strategies, two novel algorithms,  Bottom-Up and Top-Down algorithms, are  proposed to compute Skycube efficiently. Finally,  our extensive performance evaluations  confirm the effectiveness of the sharing strategies. It is
Query Translation from XPath to SQL in the Presence of Recursive DTDs.
The interaction between recursion in XPATH and  recursion in DTDs makes it challenging to answer  XPATH queries on XML data that is stored in an  RDBMS via schema-based shredding. We present  a new approach to translating XPATH queries into  SQL queries with a simple least fixpoint (LFP) operator,  which is already supported by most commercial   RDBMS. The approach is based on our  algorithm for rewriting XPATH queries into regular   XPATH expressions, which are capable of capturing  both DTD recursion and XPATH queries in  a uniform framework. Furthermore, we provide  an algorithm for translating regular XPATH queries  to SQL queries with LFP, and optimization techniques  for minimizing the use of the LFP operator.
Similarity Search with Implicit Object Features.
Abstract. Driven by many real applications, in this paper we study the problem of similarity search with implicit object features; that is, the features of each object are not pre-computed/evaluated. As the existing similarity search techniques are not applicable, a novel and efficient algorithm is developed in this paper to approach the problem. The R-tree based algorithm consists of two steps: feature evaluation and similarity search. Our performance evaluation demonstrates that the algorithm is very efficient for large spatial datasets. 1
Identifying Interesting Patterns in Multidatabases.

What makes the differences benchmarking XML database implementations.

The Predicting Power of Textual Information on Financial Markets.
Mining textual documents and time series concurrently, such as predicting the movements of stock prices based on the contents of the news stories, is an emerging topic in data mining community. Previous researches have shown that there is a strong relationship between the time when the news stories are released and the time when the stock prices fluctuate. In this paper, we propose a systematic framework for predicting the tertiary movements of stock prices by analyzing the impacts of the news stories on the stocks. To be more specific, we investigate the immediate impacts of news stories on the stocks based on the Efficient Markets Hypothesis. Several data mining and text mining techniques are used in a novel way. Extensive experiments using real-life data are conducted, and encouraging results are obtained.
Identifying Interesting Customers through Web Log Classification.

Constructing Suffix Tree for Gigabyte Sequences with Megabyte Memory.

Divide%2Dand%2DApproximate A Novel Constraint Push Strategy for Iceberg Cube Mining.

Algebraic equivalences of nested relational operators.

Dynamically Updating XML Data Numbering Scheme Revisited.

Advanced Web Technologies and Applications

Scalable sequential pattern mining for biological sequences.

Continuously Maintaining Quantile Summaries of the Most Recent N Elements over a Data Stream.
Statistics over the most recently observed data elements are often required in applications involving data streams, such as intrusion detection in network monitoring, stock price prediction in financial markets, web log mining for access prediction, and user click stream mining for personalization. Among various statistics, computing quantile summary is probably most challenging because of its complexity. In this paper, we study the problem of continuously maintaining quantile summary of the most recently observed N elements over a stream so that quantile queries can be answered with a guaranteed precision of ɛN. We developed a space efficient algorithm for pre-defined N that requires only one scan of the input data stream and O ( log(ɛ2N) ɛ + 1 ɛ2) space in the worst cases. We also developed an algorithm that maintains quantile summaries for most recent N elements so that quantile queries on any most recent n elements (n ≤ N) can be answered with a guaranteed precision of ɛn. The worst case space requirement for this algorithm is only O ( log2 (ɛN) ɛ2). Our performance study indicated that not only the actual quantile estimation error is far below the guaranteed precision but the space requirement is also much less than the given theoretical bound. 1
Classifying Text Streams in the Presence of Concept Drifts.

Data Mining Proxy Serving Large Number of Users for Efficient Frequent Itemset Mining.

False Positive or False Negative Mining Frequent Itemsets from High Speed Transactional Data Streams.

Bloom Histogram Path Selectivity Estimation for XML Data with Updates.
Cost-based XML query optimization calls for accurate estimation of the selectivity of path expressions. Some other interactive and internet applications can also benefit from such estimations. While there are a number of estimation techniques proposed in the literature, almost none of them has any guarantee on the estimation accuracy within a given space limit. In addition, most of them assume that the XML data are more or less static, i.e., with few updates. In this paper, we present a framework for XML path selectivity estimation in a dynamic context. Specifically, we propose a novel data structure, bloom histogram, to approximate XML path frequency distribution within a small space budget and to estimate the path selectivity accurately with the bloom histogram. We obtain the upper bound of its estimation error and discuss the trade-offs between the accuracy and the space limit. To support updates of bloom histograms efficiently when underlying XML data change, a dynamic summary layer is used to keep exact or more detailed XML path information. We demonstrate through our extensive experiments that the new solution can
A Simple but Effective Dynamic Materialized View Caching.

Mining Frequent Items in Spatio%2Dtemporal Databases.

Mining Dependent Patterns In Probabilistic Databases.

Efficient Mining of Frequent Patterns Using Ascending Frequency Ordered Prefix%2DTree.

An efficient strategy for mining exceptions in multi%2Ddatabases .

Selecting Views with Maintenance Cost Constraints Issues
In order to efficiently support a large number of on-line analytical processing (OLAP) queries, a data warehouse needs to precompute or materialise some of such OLAP queries. One of the important issues is how to select such a set of materialised views in order to minimise the total processing cost for OLAP queries. The maintenance-cost view-selection problem is to select a set of materialised views under a maintenance cost constraint (such as maintenance time), in order to minimise the total query processing cost for a given set of queries. This problem is more difficult than the view selection problem under a disk-space constraint, because a selected view may make the previously selected views less beneficial, due to the fact that the total maintenance cost for a set of views may decrease when more views are materialised while the maintenance cost always increases under disk-space constraint. The problem has recently received significant attention. Several greedy/heuristic algorithms were proposed. However, the quality of the greedy/heuristic algorithms has not been well analysed. In this paper, in a multidimensional data warehouse environment, we reexamine the greedy/heuristic algorithms in various settings, and provide users with insights on the quality of these heuristic algorithms. ACS Classification: H.2 (Database Management) 1.
Efficiency and Effectiveness of XML Tools and Techniques and Data Integration over the Web

M %2Dtree  A New Dynamical Multidimensional Index for Metric Spaces.

Dynamic Materialized View Management Based on Predicates.

Dynamically maintaining frequent items over a data stream.
It is challenge to maintain frequent items over a data stream, with a small bounded memory, in a dynamic environment where both insertion/deletion of items are allowed. In this paper, we propose a new novel algorithm, called hCount, which can handle both insertion and deletion of items with a much less memory space than the best reported algorithm. Our algorithm is also superior in terms of precision, recall and processing time. In addition, our approach does not request the preknowledge on the size of range for a data stream, and can handle range extension dynamically. Given a little modification, algorithm hCount can be improved to hCount*, which even owns significantly better performance than before. 1.
An Efficient and Interactive A%2A%2DAlgorithm with Pruning Power Materialized View Selection Revisited.

PathGuide An Efficient Clustering Based Indexing Method for XML Path Expressions.

Ascending Frequency Ordered Prefix%2Dtree Efficient Mining of Frequent Patterns.

AFOPT An Efficient Implementation of Pattern Growth Approach.
In this paper, we revisit the frequent itemset mining (FIM) problem and focus on studying the pattern growth approach. Existing pattern growth algorithms differ in several dimensions: (1) item search order; (2) conditional database representation; (3) conditional database construction strategy; and (4) tree traversal strategy. They adopted different strategies on these dimensions. Several adaptive algorithms were proposed to try to find good strategies for general situations. In this paper, we described the implementation techniques of an adaptive pattern growth algorithm, called AFOPT, which demonstrated good performance on all tested datasets. We also extended the algorithm to mine closed and maximal frequent itemsets. Comprehensive experiments were conducted to demonstrate the efficiency of the proposed algorithms.
Pushing Aggregate Constraints by Divide%2Dand%2DApproximate.
Iceberg-cube mining is to compute the GROUP BY partitions, for all GROUP BY dimension lists, that satisfy a given aggregate constraint. Previous works have pushed anti-monotone constraints into iceberg-cube mining. However, many useful constraints are not anti-monotone. In this paper, we propose a novel strategy for pushing general aggregate constraints, called Divide-and-Approximate. This strategy divides the search space and approximates the constraint in subspaces by a pushable constraint. As the strategy is recursively applied, the approximation approaches the given constraint and the pruning tights up. We show that all constraints defined by SQL aggregates, arithmetic operators and comparison operators can be pushed by Divideand -Approximate. We present an efficient implementation for an important subclass and evaluate it on both synthetic and real life databases.
PBiTree Coding and Efficient Processing of Containment Joins.
This paper addresses issues related to containment join processing in tree-structured data such as XML documents. A containment join takes two sets of XML node elements as input and returns pairs of elements such that the containment relationship holds between them. While there are previous algorithms for processing containment joins, they require both element sets either sorted or indexed. This paper proposes a novel and complete containment query processing framework based on a new coding scheme, PBiTree code. The PBiTree code allows us to determine the ancestor-descendant relationship between two elements from their PBiTree-based codes efficiently. We present algorithms in the framework that are optimized for various combinations of settings. In particular, the newly proposed partitioning based algorithms can process containment joins efficiently without sorting or indexes. Experimental results indicate that the containment join processing algorithms based on the proposed coding scheme outperform existing algorithms significantly. 1.
What Makes the Differences Benchmarking XML Database Implementations.

Effective Schema%2DBased XML Query Optimization Techniques.
Use of path expressions is a common feature in most XML query languages, and many evaluation methods for path expression queries have been proposed recently. However, there are few researches on the issue of optimizing regular path expression queries. In this paper, two kinds of path expression optimization principles are proposed, named path shortening and path complementing, respectively. The path shortening principle reduces the querying cost by shortening the path expressions with the knowledge of XML schema. While the path complementing principle substitutes the user queries with the equivalent lower-cost path expressions. The experimental results show that these two techniques can largely improve the performance of path expression query processing. 1
On computing%2C storing and querying frequent patterns.

HOT Hypergraph%2DBased Outlier Test for Categorical Data.
As a widely used data mining technique, outlier detection is  a process which aims to find anomalies with good explanations. Most  existing methods are designed for numeric data. However, they will meet  problems in real-life applications, which always contain categorical data.
Mining Changes of Classification by Correspondence Tracing.
We study the problem of mining changes of classification characteristics as the data changes. Available are an old classifier, representing previous knowledge about classification characteristics, and a new data. We want to find the changes of classification characteristics in the new data. An example of such changes is “members with a large family no longer shop frequently, but they used to”. Finding this kind of changes holds the key for the organization to adopt to the changed environment and stay ahead of competitors. The challenge is that it is difficult to see what has really changed from comparing the old and new classifiers that could be very large and different. In this paper, we propose a technique to identify such changes. The idea is tracing the characteristics, in the old and new classifiers, that correspond to each other by classifying the same examples. We describe several ways to present changes so that the user can focus on a small number of important ones. We evaluate the proposed method on real life data sets. 1
Containment Join Size Estimation Models and Methods.

Holistic Twig Joins on Indexed XML Documents.
Finding all the occurrences of a twig pattern  specified by a selection predicate on  multiple elements in an XML document is  a core operation for e#cient evaluation of  XML queries. Holistic twig join algorithms  were proposed recently as an optimal solution  when the twig pattern only involves ancestordescendant  relationships. In this paper, we  address the problem of e#cient processing of  holistic twig joins on all/partly indexed XML  documents. In particular, we propose an algorithm  that utilizes available indices on element  sets. While it can be shown analytically that  the proposed algorithm is as e#cient as the existing  state-of-the-art algorithms in terms of  worst case I/O and CPU cost, experimental  results on various datasets indicate that the  proposed index-based algorithm performs significantly  better than the existing ones, especially  when binary structural joins in the twig  pattern have varying join selectivities.
Classifying High%2DSpeed Text Streams.
Recently, a new class of data-intensive application becomes  widely recognized where data is modeled best as transient open-end  streams rather than persistent tables on disk. It leads to a new surge  of research interest called data streams. However, most of the reported  works are concentrated on structural data, such as bit-sequences, and  seldom focus on unstructural data, such as textual documents. In this  paper, we propose an e#cient classification approach for classifying highspeed  text streams. The proposed approach is based on sketches such that  it is able to classify the streams e#ciently by scanning them only once,  meanwhile consuming a small bounded of memory in both model maintenance  and operation. Extensive experiments using benchmarks and a  real-life news article collection are conducted. The encouraging results  indicated that our proposed approach is highly feasible.
UD%28k%2C l%29%2DIndex An Efficient Approximate Index for XML Data.

Automata Match a new XML query processing approach.

Fully Dynamic Partitioning Handling Data Skew in Parallel Data Cube Computation.

Materialized view selection as constrained evolutionary optimization.

Statistical Estimation of Access Frequencies Problems

Path Materialization Revisited An Efficient Storage Model for XML Data.
XML is emerging as a new major standard for representing data on the world wide web. Several XML storage models have been proposed to store XML data in different database management systems. The unique feature of model-mapping-based approaches is that no DTD information is required for XML data storage. In this paper, we present a new modelmapping -based storage model, called XParent. Unlike the existing work on model-mapping-based approaches that emphasized on converting XML documents to/from database schema and translation of XML queries into SQL queries, in this paper, we focus ourselves on the e#ectiveness of storage models in terms of query processing. We study the key issues that affect query performance, namely, storage schema design (storing XML data across multiple tables) and path materialization (storing path information in databases). We show that similar but di#erent storage models significantly a#ect query performance. A performance study is conducted using three data sets and query sets. The experimental results are presented.
A New Path Expression Computing Approach for XML Data.

Parallel Maintenance of Materialized Views on Personal Computer Clusters.

Condensed Cube An Efficient Approach to Reducing Data Cube Size.

XParent An Efficient RDBMS%2DBased XML Database System.

Discriminative Category Matching Efficient Text Classification for Huge Document Collections.

From Path Tree To Frequent Patterns A Framework for Mining Frequent Patterns.
In this paper, we propose a new framework for mining frequent patterns from large transactional databases. The core of the framework is of a novel coded prefix-path tree with two representations, namely, a memory-based prefixpath tree and a disk-based prefix-path tree. The disk-based prefix-path tree is simple in its data structure yet rich in information contained, and is small in size. The memorybased prefix-path tree is simple and compact. Upon the memory-based prefix-path tree, a new depth-first frequent pattern discovery algorithm, called ¢£ ¢-Mine, is proposed in this paper that outperforms FP-growth significantly. The memory-based prefix-path tree can be stored on disk using a disk-based prefix-path tree with assistance of the new coding scheme. We present efficient loading algorithms to load the minimal required disk-based prefix-path tree into main memory. Our technique is to push constraints into the loading process, which has not been well studied yet. 1.
News Sensitive Stock Trend Prediction.

Performance Evaluation of a DOM%2DBased XML Database Storage

What Difference Heuristics Make Maintenance%2DCost View%2DSelection Revisited.

Structural Map A New Index for Efficient XML Path Expression Processing.

A template model for multidimensional inter%2Dtransactional association rules.

Multi%2DCube Computation.
Computing a n-attribute datacube requires the computation of an aggregate function over all groups generated by 2  n  interrelated GROUP-BYs. In this paper, we focus on multi-cube computation. We extend the algorithms for single datacube computation to process multiple datacubes simultaneously. The issue we intend to explore is the memory utilization. We propose two multi-cube algorithms, namely, a sort-based algorithm and a hash-based algorithm. Different data skews and sparsities are investigated. Results from our extensive performance studies are reported.  1. 
Patterns Discovery Based on Time%2DSeries Decomposition.

Revisit on View Maintenance in Data Warehouses.

Support IR Query Refinement by Partial Keyword Set.

Approximate Graph Schema Extraction for Semi%2DStructured Data.

Maintaining Materialized Views for Data Warehouses with Multiple Remote Sources.

MB Tree A Dynamically Updatable Metric Index for Similarity Searches.

Optimizing Multiple Dimensional Queries Simultaneously in Multidimensional Databases.
. Multi-Dimensional Expressions (MDX) provide an interface for  asking several related OLAP queries simultaneously. An interesting problem is  how to optimize the execution of an MDX query, given that most data  warehouses maintain a set of redundant materialized views to accelerate OLAP  operations. A number of greedy and approximation algorithms have been  proposed for different versions of the problem. In this paper we evaluate  experimentally their performance using the APB and TPC-H benchmarks,  concluding that they do not scale well for realistic workloads. Motivated by this  fact, we developed two novel greedy algorithms. Our algorithms construct the  execution plan in a top-down manner by identifying in each step the most  beneficial view, instead of finding the most promising query. We show by  extensive experimentation that our methods outperform the existing ones in  most cases.  1 
Statistical estimation of access frequencies in data broadcasting environments.

Object Placement in Parallel OODBMS.

Mining Inter%2DTransaction Associations with Templates.
Multi-dimensional, inter-transaction association rules extend the traditional association rules to describe more general associations among items with multiple properties cross transactions. &#034;After McDonald and Burger King open branches, KFC will open a branch two months later and one mile away&#034; is an example of such rules. Since the number of potential inter-transaction association rules tends to be extremely large, mining inter-transaction associations poses more challenges on efficient processing than mining intra-transaction associations. In order to make such association mining truly practical and computationally tractable, in this study, we present a template model to help users declare the interesting inter-transaction associations to be mined. With the guidance of templates, several optimization techniques are devised to speed up the discovery of inter-transaction association rules. We show, through a series of experiments, that these optimization techniques can yield significa...
Hash in Place with Memory Shifting Datacube Computation Revisited.

Safe Database Queries with External Functions.

Supporting Range Queries in a Wireless Environment with Nonuniform Broadcast.

Using Stem Rules to Refine Document Retrieval Queries.

A Data Mining Approach for Query Refinement.

A Performance Study of Mobile TCP%2FIP Solutions.

Generating Broadcast Programs that Support Range Queries.

A Break for Workaholics Energy%2DEfficient Selective Tuning Mechanisms for Demand%2DDriven%2DBased Wireless Environment.

An Analysis of Selective Tuning Schemes for Nonuniform Broadcast.

A Dynamic Scheduler for the Infinite Air%2DCache.

On Balancing Workload in a Highly Mobile Environment.
. We describe the complete factorization of the tenth and eleventh Fermat numbers. The tenth Fermat number is a product of four prime factors with 8, 10, 40 and 252 decimal digits. The eleventh Fermat number is a product of five prime factors with 6, 6, 21, 22 and 564 decimal digits. We also note a new 27-decimal digit factor of the thirteenth Fermat number. This number has four known prime factors and a 2391-decimal digit composite factor. All the new factors reported here were found by the elliptic curve method (ECM). The 40-digit factor of the tenth Fermat number was found after about 140 Mflop-years of computation. We discuss aspects of the practical implementation of ECM, including the use of special-purpose hardware, and note several other large factors found recently by ECM. 1. Introduction  For a nonnegative integer n, the n-th Fermat number is F n = 2  2  n  + 1. It is known that F n is prime for 0  n  4, and composite for 5  n  23. Also, for n  2, the factors of F n are of th...
Scheduling Issues in Partitioned Temporal Join.
Many matrices that arise in the solution of signal processing problems have a special  displacement structure. For example, adaptive filtering and direction-of-arrival estimation yield matrices of Toeplitz type. A recent method of Gohberg, Kailath and Olshevsky (GKO) allows fast Gaussian elimination with partial pivoting for such structured matrices. In this paper, a rounding error analysis is performed on the Cauchy and Toeplitz variants of the GKO method. It is shown the error growth depends on the growth in certain auxiliary vectors, the generators, which are computed by the GKO algorithms. It is also shown that in certain circumstances, the growth in the generators can be large, and so the error growth is much larger than would be encountered with normal Gaussian elimination with partial pivoting. A modification of the algorithm to perform a type of row-column pivoting is proposed which may ameliorate this problem.  Keywords: Structured matrices, fast algorithms, displacement rank,...
On Translation of Complex Value Calculus Queries with Arithmatic Operators.

Energy Efficient Filtering of Nonuniform Broadcast.

A Performance Study of Declustering Strategies for Parallel Spatial Databases

Spatial Join Strategies in Distributed Spatial DBMS.

A Guideline for Implementing Access Method Modules in Extensible DBMS MODUS.

LRU%2DS A New Buffer Allocation Approach for OODBMS.

Decomposition %2D An Approach for Optimizing Queries Including ADT Functions.

Integration of Functional Data Model into Programming Environment Application to Solid Database.

Database support for solid modeling.

